1. Field
This disclosure relates to networks, and more particularly to routing methods in convergecast networking.
2. Description of Related Art
Many sensor network applications require broadcast and convergecast for data dissemination or collection. Convergecast generally refers to a communication pattern in which the flow of data takes place from a set of nodes toward a single node in a network. Convergecast can be viewed as the opposite of broadcast or multicast, in which the flow of data takes place from a single node to a set of nodes in the network. FIG. 1 is a simple example that illustrates the characteristics of both broadcast and convergecast in a network. On the left-hand side is a broadcast example in which node A is the message source and nodes B, C, D are the expected recipients. Node B hears or receives node A's message directly, and forwards a copy of the message to nodes C and D. On the right-hand side is a convergecast example in which node A is the destination node. Nodes B, C, and D each have a message destined to node A. In this example, node B serves as the forwarding node, which is a relay node for nodes C and D.
The issue of designing efficient and reliable broadcast protocols for wireless ad hoc networks has received much attention in recent years. However, the issue of convergecast has only rarely been addressed. At first glance, it may appear that convergecast is the reverse process of broadcast. However, there is at least one critical difference between convergecast and broadcast that makes convergecast more than merely the reverse process of broadcast. In broadcast, the data being disseminated is identical for all recipients. As a result, the data only needs to traverse any edge in the network at most once, and the bandwidth utilization for broadcast process is essentially uniform across the entire network. On the other hand, convergecast is a many-to-one process wherein the data flowing to the recipient from different nodes are likely to be different. The result generally is a non-uniform bandwidth demand across the network because, for example, more bandwidth is needed for nodes closer to the sink, as seen in the illustration of FIG. 1. In the convergecast process illustrated in FIG. 1, the edge BA is traversed by three packets while edges CB and DB are traversed by only one packet.
It should be noted that in wireless networks, collision is a major adversary to communication reliability, and wastes resources (energy, bandwidth, time). Collisions generally occur when multiple nodes simultaneously transmit over the same channel to the same node, or when a receiver is in the range of another transmission over the same channel. Many schemes, especially Media Access Control (MAC) level ones, such as Carrier-Sense-Multiple-Access (CSMA), Carrier-Sense-Multiple-Access with Collision Avoidance (CSMA/CA), Frequency-Division Multiple Access (FDMA), Code-Division-Multiple-Access (CDMA), Time-Division-Multiple-Access (TDMA), have been proposed and used to reduce collisions in wireless communication. The concern for simplicity and scalability for large scale wireless sensor networks has led to the adoption of CSMA and its close variants such as the MAC layer strategies in the popular Mica mote platform.